<!doctype html>
<html lang="en">
<head><meta name="generator" content="Hexo 3.9.0">
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, user-scalable=no, initial-scale=1.0, maximum-scale=1.0, minimum-scale=1.0">
    <meta http-equiv="X-UA-Compatible" content="ie=edge">
    <title>言成言成啊</title>
    <link rel="shortcut icon" href="/images/favicon.ico">
    <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/meethigher/cdn@9.0/css/meethigher-font.css">
    <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/meethigher/cdn@9.0/css/animate.css">
    <link rel="stylesheet" href="/css/index.css">
</head>
<body>
<header class="header">
    <div class="header-menu"><span class="fa fa-bars"></span></div>
    <div class="header-search"><span class="fa fa-search"></span></div>
    <div class="header-title"><a href="/">言成言成啊 | <span class="header-subtitle">Kit Chen&#39;s Blog</span></a></div>
    <ul class="header-navbar clearFix">
        
            <li><a href="/">主页</a></li>
        
            <li><a href="/tags">标签</a></li>
        
            <li><a href="/archives">归档</a></li>
        
            <li><a href="/search">导航</a></li>
        
    </ul>
</header>
<main class="main">
    <div class="main-content meethigher-scroll">
    <article class="post">
        <div class="post-title">
            <h2 class="title">常用的数据结构</h2>
        </div>
        <div class="post-media2">
            <span class="post-time">2019-10-15</span>
            
                <ul class="article-tag-list"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/data-structure/">data-structure</a></li></ul>
            
        </div>
        <div class="post-content blog-markdown">
            <h1 id="数据结构"><a href="#数据结构" class="headerlink" title="数据结构"></a>数据结构</h1><h2 id="1-数据结构有什么用？"><a href="#1-数据结构有什么用？" class="headerlink" title="1 数据结构有什么用？"></a>1 数据结构有什么用？</h2><p>当你用着java里面的容器类很爽的时候，你有没有想过，怎么ArrayList就像一个无限扩充的数组，也好像链表之类的。好用吗？好用，这就是数据结构的用处，只不过你在不知不觉中使用了。</p>
<p>现实世界的存储，我们使用的工具和建模。每种数据结构有自己的优点和缺点，想想如果Google的数据用的是数组的存储，我们还能方便地查询到所需要的数据吗？而算法，在这么多的数据中如何做到最快的插入，查找，删除，也是在追求更快。</p>
<p>我们java是面向对象的语言，就好似自动档轿车，C语言好似手动档吉普。数据结构呢？是变速箱的工作原理。你完全可以不知道变速箱怎样工作，就把自动档的车子从 A点 开到 B点，而且未必就比懂得的人慢。写程序这件事，和开车一样，经验可以起到很大作用，但如果你不知道底层是怎么工作的，就永远只能开车，既不会修车，也不能造车。当然了，数据结构内容比较多，细细的学起来也是相对费功夫的，不可能达到一蹴而就。我们将常见的数据结构：堆栈、队列、数组、链表和红黑树 这几种给大家介绍一下，作为数据结构的入门，了解一下它们的特点即可。</p>
<img src="/2019/10/15/data-structure/数据结构比喻.png" title="数据结构比喻">

<h2 id="2-常见的数据结构"><a href="#2-常见的数据结构" class="headerlink" title="2 常见的数据结构"></a>2 常见的数据结构</h2><p>数据存储的常用结构有：栈、队列、数组、链表和红黑树。我们分别来了解一下：</p>
<h4 id="栈"><a href="#栈" class="headerlink" title="栈"></a>栈</h4><ul>
<li><strong>栈</strong>：<strong>stack</strong>,又称堆栈，它是运算受限的线性表，其限制是仅允许在标的一端进行插入和删除操作，不允许在其他任何位置进行添加、查找、删除等操作。</li>
</ul>
<p>简单的说：采用该结构的集合，对元素的存取有如下的特点</p>
<ul>
<li>先进后出（即，存进去的元素，要在后它后面的元素依次取出后，才能取出该元素）。例如，子弹压进弹夹，先压进去的子弹在下面，后压进去的子弹在上面，当开枪时，先弹出上面的子弹，然后才能弹出下面的子弹。</li>
<li>栈的入口、出口的都是栈的顶端位置。</li>
</ul>
<img src="/2019/10/15/data-structure/堆栈.png" title="堆栈">

<p>这里两个名词需要注意：</p>
<ul>
<li><strong>压栈</strong>：就是存元素。即，把元素存储到栈的顶端位置，栈中已有元素依次向栈底方向移动一个位置。</li>
<li><strong>弹栈</strong>：就是取元素。即，把栈的顶端位置元素取出，栈中已有元素依次向栈顶方向移动一个位置。</li>
</ul>
<h4 id="队列"><a href="#队列" class="headerlink" title="队列"></a>队列</h4><ul>
<li><strong>队列</strong>：<strong>queue</strong>,简称队，它同堆栈一样，也是一种运算受限的线性表，其限制是仅允许在表的一端进行插入，而在表的另一端进行删除。</li>
</ul>
<p>简单的说，采用该结构的集合，对元素的存取有如下的特点：</p>
<ul>
<li>先进先出（即，存进去的元素，要在后它前面的元素依次取出后，才能取出该元素）。例如，小火车过山洞，车头先进去，车尾后进去；车头先出来，车尾后出来。</li>
<li>队列的入口、出口各占一侧。例如，下图中的左侧为入口，右侧为出口。</li>
</ul>
<img src="/2019/10/15/data-structure/队列图.bmp" title="队列图">

<h4 id="数组"><a href="#数组" class="headerlink" title="数组"></a>数组</h4><ul>
<li><strong>数组</strong>:<strong>Array</strong>,是有序的元素序列，数组是在内存中开辟一段连续的空间，并在此空间存放元素。就像是一排出租屋，有100个房间，从001到100每个房间都有固定编号，通过编号就可以快速找到租房子的人。</li>
</ul>
<p>简单的说,采用该结构的集合，对元素的存取有如下的特点：</p>
<ul>
<li>查找元素快：通过索引，可以快速访问指定位置的元素</li>
</ul>
<img src="/2019/10/15/data-structure/数组查询快.png" title="数组查询快">

<ul>
<li><p>增删元素慢</p>
<ul>
<li><strong>指定索引位置增加元素</strong>：需要创建一个新数组，将指定新元素存储在指定索引位置，再把原数组元素根据索引，复制到新数组对应索引的位置。如下图</li>
</ul>
<img src="/2019/10/15/data-structure/数组添加.png" title="数组添加">

<ul>
<li><strong>指定索引位置删除元素：</strong>需要创建一个新数组，把原数组元素根据索引，复制到新数组对应索引的位置，原数组中指定索引位置元素不复制到新数组中。如下图</li>
</ul>
<img src="/2019/10/15/data-structure/数组删除.png" title="数组删除">



</li>
</ul>
<h4 id="链表"><a href="#链表" class="headerlink" title="链表"></a>链表</h4><ul>
<li><strong>链表</strong>:<strong>linked list</strong>,由一系列结点node（链表中每一个元素称为结点）组成，结点可以在运行时i动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。我们常说的链表结构有单向链表与双向链表，那么这里给大家介绍的是<strong>单向链表</strong>。</li>
</ul>
<img src="/2019/10/15/data-structure/单链表结构特点.png" title="单链表结构特点">

<p>简单的说，采用该结构的集合，对元素的存取有如下的特点：</p>
<ul>
<li>多个结点之间，通过地址进行连接。例如，多个人手拉手，每个人使用自己的右手拉住下个人的左手，依次类推，这样多个人就连在一起了。</li>
</ul>
<img src="/2019/10/15/data-structure/单链表结构.png" title="单链表结构">

<ul>
<li><p>查找元素慢：想查找某个元素，需要通过连接的节点，依次向后查找指定元素</p>
</li>
<li><p>增删元素快：</p>
<ul>
<li>增加元素：只需要修改连接下个元素的地址即可。</li>
</ul>
<img src="/2019/10/15/data-structure/增加结点.png" title="增加结点">

<ul>
<li>删除元素：只需要修改连接下个元素的地址即可。</li>
</ul>
<img src="/2019/10/15/data-structure/删除结点.bmp" title="删除节点">

</li>
</ul>
<h4 id="红黑树"><a href="#红黑树" class="headerlink" title="红黑树"></a>红黑树</h4><ul>
<li><strong>二叉树</strong>：<strong>binary tree</strong> ,是每个结点不超过2的有序<strong>树（tree）</strong> 。</li>
</ul>
<p>简单的理解，就是一种类似于我们生活中树的结构，只不过每个结点上都最多只能有两个子结点。</p>
<p>二叉树是每个节点最多有两个子树的树结构。顶上的叫根结点，两边被称作“左子树”和“右子树”。</p>
<p>如图：</p>
<img src="/2019/10/15/data-structure/二叉树.bmp" title="二叉树">

<p>我们要说的是二叉树的一种比较有意思的叫做<strong>红黑树</strong>，红黑树本身就是一颗二叉查找树，将节点插入后，该树仍然是一颗二叉查找树。也就意味着，树的键值仍然是有序的。</p>
<p>红黑树的约束:</p>
<ol>
<li>节点可以是红色的或者黑色的</li>
</ol>
<ol start="2">
<li>根节点是黑色的</li>
</ol>
<ol start="3">
<li>叶子节点(特指空节点)是黑色的</li>
<li>每个红色节点的子节点都是黑色的</li>
<li>任何一个节点到其每一个叶子节点的所有路径上黑色节点数相同</li>
</ol>
<p>红黑树的特点:</p>
<p>​    速度特别快,趋近平衡树,查找叶子元素最少和最多次数不多于二倍</p>
        </div>
        
            <div class="busuanzi">
                <span id="busuanzi_container_page_pv">阅读量<span id="busuanzi_value_page_pv"></span>次</span>
                <script async src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>
            </div>
        
    </article>
</div>
    <pointer href="javascript:void(0);" class="arrow fa fa-arrow-up"></pointer>
<pointer href="javascript:void(0);" class="arrow fa fa-arrow-down"></pointer>

</main>
<aside class="aside">
    <div class="aside-content">
        <div class="aside-avatar"><img src="/images/kitchen.jpg" alt="言成"></div>
        <div class="aside-author">言成</div>
        <div class="aside-description">爱学习，爱运动，爱看妹子</div>
        <ul class="aside-contact clearFix">
            <li><span class="fa fa-github"></span><a href="https://github.com/meethigher">Github</a></li>
            <li><span class="fa fa-envelope"></span><a href="javascript:void(0);">meethigher@qq.com</a></li>
            <li><span class="fa fa-weixin"></span><a href="javascript:void(0);"><img src="/images/weixin.png" alt="扫描微信二维码，加我哦！"></a></li>
        </ul>
    </div>
</aside>
<div class="toolbar"><span class="fa fa-th"></span></div>
<div id="particles-js"></div>
<script src="https://cdn.jsdelivr.net/gh/meethigher/cdn@9.0/js/jquery.min.js"></script>
<script src="https://cdn.jsdelivr.net/gh/meethigher/cdn@9.0/js/particles.min.js"></script>
<script src="https://cdn.jsdelivr.net/gh/meethigher/cdn@9.0/js/app.js"></script>
<script src="/js/meethigher.js"></script>
<script src="/js/toolbar.js"></script>
</body>
</html>